Series-Parallel Planar Ordered Sets Have Pagenumber Two (Extended Abstract)

摘要

The page number of a series-parallel planar P is at most two. We present an O(n^3) algorithm to construct a two-page embedding in the case that it is a lattice. One consequence of independent interest, is a characterization of series-parallel planar ordered sets.